package com.zp.self.module.level_4_算法练习.数据结构.二叉树;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author By ZengPeng
 */
public class 力扣_98_验证二叉搜索树 {
    @Test
    public void main() {

        System.out.println(isValidBST(TreeNode.initRoot()));
    }

    /**
    题目：给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
         有效 二叉搜索树定义如下：
         节点的左子树只包含 小于 当前节点的数。
         节点的右子树只包含 大于 当前节点的数。
         所有左子树和右子树自身必须也是二叉搜索树。

     示例 1：
     输入：root = [2,1,3]
     输出：true

     示例 2：
     输入：root = [5,1,4,null,null,3,6]
     输出：false
     解释：根节点的值是 5 ，但是右子节点的值是 4 。

    分析：【P 💜💜】
       1.中序遍历：是否递增
                优化：空间的优化，可以使用long.min 充当第一个值，避免最小值是int.min
                --执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     
    边界值 & 注意点：
       1.父节点，要大于所有左子节点
     **/
    public boolean isValidBST(TreeNode c) {
        List<Integer>  list = new ArrayList<>();
        return dfs(c,list);
    }

    private boolean dfs(TreeNode c, List<Integer> list) {
        if(c==null) return true;
        if(!dfs(c.left, list) || (!list.isEmpty() &&  c.val<=list.get(list.size()-1)))
            return false;
        list.add(c.val);
        return dfs(c.right,list);
    }
}
